SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Scheduling (computing)</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Scheduling (computing)</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about scheduling of computing resources. For networks, see <a href="Network_scheduler" title="Network scheduler">Network scheduler</a>. For other uses, see <a href="Scheduling_(disambiguation)" class="mw-redirect mw-disambig" title="Scheduling (disambiguation)">Scheduling (disambiguation)</a>.</div>

<p>In <a href="Computing" title="Computing">computing</a>, <b>scheduling</b> is the action of assigning <a href="System_resource" title="System resource">resources</a> to perform <a href="Task_(computing)" title="Task (computing)">tasks</a>. The resources may be <a href="Central_processing_unit" title="Central processing unit">processors</a>, <a href="Telecommunications_link" title="Telecommunications link">network links</a> or <a href="Expansion_card" title="Expansion card">expansion cards</a>. The tasks may be <a href="Thread_(computer_science)" class="mw-redirect" title="Thread (computer science)">threads</a>, <a href="Process_(computing)" title="Process (computing)">processes</a> or data <a href="Traffic_flow_(computer_networking)" title="Traffic flow (computer networking)">flows</a>.

</p><p>The scheduling activity is carried out by a mechanism called a <b>scheduler</b>. Schedulers are often designed so as to keep all computer resources busy (as in <a href="Load_balancing_(computing)" title="Load balancing (computing)">load balancing</a>), allow multiple users to share system resources effectively, or to achieve a target <a href="Quality-of-service" class="mw-redirect" title="Quality-of-service">quality-of-service</a>.

</p><p>Scheduling is fundamental to computation itself, and an intrinsic part of the <a href="Execution_model" title="Execution model">execution model</a> of a computer system; the concept of scheduling makes it possible to have <a href="Computer_multitasking" title="Computer multitasking">computer multitasking</a> with a single <a href="Central_processing_unit" title="Central processing unit">central processing unit</a> (CPU).

</p>

<div class="mw-heading mw-heading2"><h2 id="Goals">Goals</h2></div>

<p>A scheduler may aim at one or more goals, for example:

</p>

<ul><li>maximizing <i><a href="Throughput" class="mw-redirect" title="Throughput">throughput</a></i> (the total amount of work completed per time unit);</li>

<li>minimizing <i><a href="Computer_performance#Response_time" title="Computer performance">wait time</a></i> (time from work becoming ready until the first point it begins execution);</li>

<li>minimizing <i><a href="Latency_(engineering)" title="Latency (engineering)">latency</a></i> or <i><a href="Response_time_(technology)" title="Response time (technology)">response time</a></i> (time from work becoming ready until it is finished in case of batch activity,<sup id="cite_ref-liu1973_1-0" class="reference"><a href="#cite_note-liu1973-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-kleinrock1976_2-0" class="reference"><a href="#cite_note-kleinrock1976-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-feitelson2014_3-0" class="reference"><a href="#cite_note-feitelson2014-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> or until the system responds and hands the first output to the user in case of interactive activity);<sup id="cite_ref-silberschatz2012_4-0" class="reference"><a href="#cite_note-silberschatz2012-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></li>

<li>maximizing <i>fairness</i> (equal CPU time to each process, or more generally appropriate times according to the priority and workload of each process).</li></ul>

<p>In practice, these goals often conflict (e.g. throughput versus latency), thus a scheduler will implement a suitable compromise. Preference is measured by any one of the concerns mentioned above, depending upon the user's needs and objectives.

</p><p>In <a href="Real-time_computing" title="Real-time computing">real-time</a> environments, such as <a href="Embedded_system" title="Embedded system">embedded systems</a> for <a href="Automatic_control" class="mw-redirect" title="Automatic control">automatic control</a> in industry (for example <a href="Robotics" title="Robotics">robotics</a>), the scheduler also must ensure that processes can meet <a href="Time_limit" title="Time limit">deadlines</a>; this is crucial for keeping the system stable. Scheduled tasks can also be distributed to remote devices across a network and <a href="Device_Management" class="mw-redirect" title="Device Management">managed</a> through an administrative back end.

</p>

<div class="mw-heading mw-heading2"><h2 id="Types_of_operating_system_schedulers">Types of operating system schedulers</h2></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Network_scheduler" title="Network scheduler">Network scheduler</a>, <a href="I/O_scheduling" title="I/O scheduling">I/O scheduling</a>, and <a href="Job_scheduler" title="Job scheduler">Job scheduler</a></div>

<p>The scheduler is an operating system module that selects the next jobs to be admitted into the system and the next process to run. Operating systems may feature up to three distinct scheduler types: a <i>long-term scheduler</i> (also known as an admission scheduler or high-level scheduler), a <i>mid-term or medium-term scheduler</i>, and a <i>short-term scheduler</i>. The names suggest the relative frequency with which their functions are performed.

</p>

<div class="mw-heading mw-heading3"><h3 id="Process_scheduler">Process scheduler</h3></div>

<p>The process scheduler is a part of the operating system that decides which process runs at a certain point in time. It usually has the ability to pause a running process, move it to the back of the running queue and start a new process; such a scheduler is known as a <i><a href="Preemption_(computing)" title="Preemption (computing)">preemptive</a> scheduler</i>, otherwise it is a <i><a href="Nonpreemptive_multitasking" class="mw-redirect" title="Nonpreemptive multitasking">cooperative</a> scheduler</i>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p><p>We distinguish between <i>long-term scheduling</i>, <i>medium-term scheduling</i>, and <i>short-term scheduling</i> based on how often decisions must be made.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading4"><h4 id="Long-term_scheduling">Long-term scheduling</h4></div>

<p>The <i>long-term scheduler</i>, or <i>admission scheduler</i>, decides which jobs or processes are to be admitted to the ready queue (in main memory); that is, when an attempt is made to execute a program, its admission to the set of currently executing processes is either authorized or delayed by the long-term scheduler. Thus, this scheduler dictates what processes are to run on a system, the degree of concurrency to be supported at any one time – whether many or few processes are to be executed concurrently, and how the split between I/O-intensive and CPU-intensive processes is to be handled. The long-term scheduler is responsible for controlling the degree of multiprogramming.

</p><p>In general, most processes can be described as either <a href="I/O-bound" class="mw-redirect" title="I/O-bound">I/O-bound</a> or <a href="CPU-bound" title="CPU-bound">CPU-bound</a>. An I/O-bound process is one that spends more of its time doing I/O than it spends doing computations. A CPU-bound process, in contrast, generates I/O requests infrequently, using more of its time doing computations. It is important that a long-term scheduler selects a good process mix of I/O-bound and CPU-bound processes. If all processes are I/O-bound, the ready queue will almost always be empty, and the short-term scheduler will have little to do. On the other hand, if all processes are CPU-bound, the I/O waiting queue will almost always be empty, devices will go unused, and again the system will be unbalanced. The system with the best performance will thus have a combination of CPU-bound and I/O-bound processes. In modern operating systems, this is used to make sure that real-time processes get enough CPU time to finish their tasks.<sup id="cite_ref-Galvin_7-0" class="reference"><a href="#cite_note-Galvin-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p><p>Long-term scheduling is also important in large-scale systems such as <a href="Batch_processing" title="Batch processing">batch processing</a> systems, <a href="Computer_cluster" title="Computer cluster">computer clusters</a>, <a href="Supercomputer" title="Supercomputer">supercomputers</a>, and <a href="Render_farm" title="Render farm">render farms</a>. For example, in <a href="Concurrent_computing" title="Concurrent computing">concurrent systems</a>, <a href="Coscheduling" title="Coscheduling">coscheduling</a> of interacting processes is often required to prevent them from blocking due to waiting on each other. In these cases, special-purpose <a href="Job_scheduler" title="Job scheduler">job scheduler</a> software is typically used to assist these functions, in addition to any underlying admission scheduling support in the operating system.

</p><p>Some operating systems only allow new tasks to be added if it is sure all real-time deadlines can still be met.

The specific heuristic algorithm used by an operating system to accept or reject new tasks is the <i>admission control mechanism</i>.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading4"><h4 id="Medium-term_scheduling">Medium-term scheduling</h4></div>

<p>The <i>medium-term scheduler</i> temporarily removes processes from main memory and places them in secondary memory (such as a <a href="Hard_disk_drive" title="Hard disk drive">hard disk drive</a>) or vice versa, which is commonly referred to as <i>swapping out</i> or <i>swapping in</i> (also incorrectly as <i><a href="Paging" class="mw-redirect" title="Paging">paging</a> out</i> or <i>paging in</i>). The medium-term scheduler may decide to swap out a process that has not been active for some time, a process that has a low priority, a process that is <a href="Page_fault" title="Page fault">page faulting</a> frequently, or a process that is taking up a large amount of memory in order to free up main memory for other processes, swapping the process back in later when more memory is available, or when the process has been unblocked and is no longer waiting for a resource.

</p><p>In many systems today (those that support mapping virtual address space to secondary storage other than the swap file), the medium-term scheduler may actually perform the role of the long-term scheduler, by treating binaries as <i>swapped-out processes</i> upon their execution. In this way, when a segment of the binary is required it can be swapped in on demand, or <i>lazy loaded</i>, also called <a href="Demand_paging" title="Demand paging">demand paging</a>.

</p>

<div class="mw-heading mw-heading4"><h4 id="Short-term_scheduling">Short-term scheduling</h4></div>

<p>The <i>short-term scheduler</i> (also known as the <i>CPU scheduler</i>) decides which of the ready, in-memory processes is to be executed (allocated a CPU) after a clock <a href="Interrupt" title="Interrupt">interrupt</a>, an I/O interrupt, an operating <a href="System_call" title="System call">system call</a> or another form of <a href="Signal_programming" class="mw-redirect" title="Signal programming">signal</a>. Thus the short-term scheduler makes scheduling decisions much more frequently than the long-term or mid-term schedulers – A scheduling decision will at a minimum have to be made after every time slice, and these are very short. This scheduler can be <a href="Preemption_(computing)" title="Preemption (computing)">preemptive</a>, implying that it is capable of forcibly removing processes from a CPU when it decides to allocate that CPU to another process, or non-preemptive (also known as <i>voluntary</i> or <i>co-operative</i>), in which case the scheduler is unable to <i>force</i> processes off the CPU.

</p><p>A preemptive scheduler relies upon a <a href="Programmable_interval_timer" title="Programmable interval timer">programmable interval timer</a> which invokes an <a href="Interrupt_handler" title="Interrupt handler">interrupt handler</a> that runs in <a href="Kernel_mode" class="mw-redirect" title="Kernel mode">kernel mode</a> and implements the scheduling function.

</p>

<div class="mw-heading mw-heading4"><h4 id="Dispatcher">Dispatcher</h4></div>

<p>Another component that is involved in the CPU-scheduling function is the dispatcher, which is the module that gives control of the CPU to the process selected by the short-term scheduler. It receives control in kernel mode as the result of an interrupt or system call. The functions of a dispatcher involve the following:

</p>

<ul><li><a href="Context_switch" title="Context switch">Context switches</a>, in which the dispatcher saves the <a href="State_(computer_science)" title="State (computer science)">state</a> (also known as <a href="Context_(computing)" title="Context (computing)">context</a>) of the <a href="Process_(computing)" title="Process (computing)">process</a> or <a href="Thread_(computing)" title="Thread (computing)">thread</a> that was previously running; the dispatcher then loads the initial or previously saved state of the new process.</li>

<li>Switching to user mode.</li>

<li>Jumping to the proper location in the user program to restart that program indicated by its new state.</li></ul>

<p>The dispatcher should be as fast as possible since it is invoked during every process switch. During the context switches, the processor is virtually idle for a fraction of time, thus unnecessary context switches should be avoided. The time it takes for the dispatcher to stop one process and start another is known as the <i>dispatch latency</i>.<sup id="cite_ref-Galvin_7-1" class="reference"><a href="#cite_note-Galvin-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 155">: 155 </span></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Scheduling_disciplines">Scheduling disciplines</h2></div>

<p>A <b>scheduling discipline</b> (also called <b>scheduling policy</b> or <b>scheduling algorithm</b>) is an algorithm used for distributing resources among parties which simultaneously and asynchronously request them. Scheduling disciplines are used in <a href="Router_(computing)" title="Router (computing)">routers</a> (to handle packet traffic) as well as in <a href="Operating_system" title="Operating system">operating systems</a> (to share <a href="CPU_time" title="CPU time">CPU time</a> among both <a href="Thread_(computer_science)" class="mw-redirect" title="Thread (computer science)">threads</a> and <a href="Process_(computing)" title="Process (computing)">processes</a>), disk drives (<a href="I/O_scheduling" title="I/O scheduling">I/O scheduling</a>), printers (<a href="Print_spooler" class="mw-redirect" title="Print spooler">print spooler</a>), most embedded systems, etc.

</p><p>The main purposes of scheduling algorithms are to minimize <a href="Resource_starvation" class="mw-redirect" title="Resource starvation">resource starvation</a> and to ensure fairness amongst the parties utilizing the resources. Scheduling deals with the problem of deciding which of the outstanding requests is to be allocated resources. There are many different scheduling algorithms. In this section, we introduce several of them.

</p><p>In <a href="Packet-switched" class="mw-redirect" title="Packet-switched">packet-switched</a> <a href="Computer_networks" class="mw-redirect" title="Computer networks">computer networks</a> and other <a href="Statistical_multiplexing" class="mw-redirect" title="Statistical multiplexing">statistical multiplexing</a>, the notion of a <b>scheduling algorithm</b> is used as an alternative to <a href="FIFO_(computing_and_electronics)" title="FIFO (computing and electronics)">first-come first-served</a> queuing of data packets.

</p><p>The simplest best-effort scheduling algorithms are <a href="Round-robin_scheduling" title="Round-robin scheduling">round-robin</a>, <a href="Fair_queuing" title="Fair queuing">fair queuing</a> (a <a href="Max-min_fair" class="mw-redirect" title="Max-min fair">max-min fair</a> scheduling algorithm), <a href="Proportional-fair_scheduling" title="Proportional-fair scheduling">proportional-fair scheduling</a> and <a href="Maximum_throughput_scheduling" title="Maximum throughput scheduling">maximum throughput</a>. If differentiated or guaranteed <a href="Quality_of_service" title="Quality of service">quality of service</a> is offered, as opposed to best-effort communication, <a href="Weighted_fair_queuing" class="mw-redirect" title="Weighted fair queuing">weighted fair queuing</a> may be utilized.

</p><p>In advanced packet radio wireless networks such as <a href="HSDPA" class="mw-redirect" title="HSDPA">HSDPA</a> (High-Speed Downlink Packet Access) <a href="3.5G" class="mw-redirect" title="3.5G">3.5G</a> cellular system, <b>channel-dependent scheduling</b> may be used to take advantage of <a href="Channel_state_information" title="Channel state information">channel state information</a>. If the channel conditions are favourable, the <a href="Throughput" class="mw-redirect" title="Throughput">throughput</a> and <a href="System_spectral_efficiency" class="mw-redirect" title="System spectral efficiency">system spectral efficiency</a> may be increased. In even more advanced systems such as <a href="LTE_Advanced" title="LTE Advanced">LTE</a>, the scheduling is combined by channel-dependent packet-by-packet <a href="Dynamic_channel_allocation" class="mw-redirect" title="Dynamic channel allocation">dynamic channel allocation</a>, or by assigning <a href="OFDMA" class="mw-redirect" title="OFDMA">OFDMA</a> multi-carriers or other <a href="Frequency-domain_equalization" class="mw-redirect" title="Frequency-domain equalization">frequency-domain equalization</a> components to the users that best can utilize them.<sup id="cite_ref-Miao_9-0" class="reference"><a href="#cite_note-Miao-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="First_come,_first_served">First come, first served</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="FIFO_(computing_and_electronics)" title="FIFO (computing and electronics)">FIFO (computing and electronics)</a></div>

<p><i>First in, first out</i> (<a href="FIFO_(computing_and_electronics)" title="FIFO (computing and electronics)">FIFO</a>), also known as <i>first come, first served</i> (FCFS), is the simplest scheduling algorithm. FIFO simply queues processes in the order that they arrive in the ready queue. This is commonly used for a <b><style data-mw-deduplicate="TemplateStyles:r1238216509">

/* start https://en.wikipedia.org/ */

.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}@media screen{html.skin-theme-clientpref-night .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}

/* end https://en.wikipedia.org/ */

</style><span class="vanchor"><span class="vanchor-text">task queue</span></span></b>, for example as illustrated in this section.

</p>

<ul><li>Since context switches only occur upon process termination, and no reorganization of the process queue is required, scheduling overhead is minimal.</li>

<li>Throughput can be low, because long processes can be holding the CPU, causing the short processes to wait for a long time (known as the convoy effect).</li>

<li>No starvation, because each process gets chance to be executed after a definite time.</li>

<li><a href="Turnaround_time" title="Turnaround time">Turnaround time</a>, waiting time and response time depend on the order of their arrival and can be high for the same reasons above.</li>

<li>No prioritization occurs, thus this system has trouble meeting process deadlines.</li>

<li>The lack of prioritization means that as long as every process eventually completes, there is no starvation. In an environment where some processes might not complete, there can be starvation.</li>

<li>It is based on queuing.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Priority_scheduling">Priority scheduling</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Earliest_deadline_first_scheduling" title="Earliest deadline first scheduling">Earliest deadline first scheduling</a></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Deadline-monotonic_scheduling" title="Deadline-monotonic scheduling">Deadline-monotonic scheduling</a></div>

<p>Earliest deadline first (EDF) or <i>least time to go</i> is a dynamic scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs (a task finishes, new task is released, etc.), the queue will be searched for the process closest to its deadline, which will be the next to be scheduled for execution.

</p>

<div class="mw-heading mw-heading3"><h3 id="Shortest_remaining_time_first">Shortest remaining time first</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Shortest_remaining_time" title="Shortest remaining time">Shortest remaining time</a></div>

<p>Similar to <a href="Shortest_job_first" class="mw-redirect" title="Shortest job first">shortest job first</a> (SJF). With this strategy the scheduler arranges processes with the least estimated processing time remaining to be next in the queue. This requires advanced knowledge or estimations about the time required for a process to complete.

</p>

<ul><li>If a shorter process arrives during another process' execution, the currently running process is interrupted (known as preemption), dividing that process into two separate computing blocks. This creates excess overhead through additional context switching. The scheduler must also place each incoming process into a specific place in the queue, creating additional overhead.</li>

<li>This algorithm is designed for maximum throughput in most scenarios.</li>

<li>Waiting time and response time increase as the process's computational requirements increase. Since turnaround time is based on waiting time plus processing time, longer processes are significantly affected by this. Overall waiting time is smaller than FIFO, however since no process has to wait for the termination of the longest process.</li>

<li>No particular attention is given to deadlines, the programmer can only attempt to make processes with deadlines as short as possible.</li>

<li>Starvation is possible, especially in a busy system with many small processes being run.</li>

<li>To use this policy we should have at least two processes of different priority</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Fixed-priority_pre-emptive_scheduling">Fixed-priority pre-emptive scheduling</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Fixed-priority_pre-emptive_scheduling" title="Fixed-priority pre-emptive scheduling">Fixed-priority pre-emptive scheduling</a></div>

<p>The operating system assigns a fixed-priority rank to every process, and the scheduler arranges the processes in the ready queue in order of their priority. Lower-priority processes get interrupted by incoming higher-priority processes.

</p>

<ul><li>Overhead is not minimal, nor is it significant.</li>

<li>FPPS has no particular advantage in terms of throughput over FIFO scheduling.</li>

<li>If the number of rankings is limited, it can be characterized as a collection of FIFO queues, one for each priority ranking. Processes in lower-priority queues are selected only when all of the higher-priority queues are empty.</li>

<li>Waiting time and response time depend on the priority of the process. Higher-priority processes have smaller waiting and response times.</li>

<li>Deadlines can be met by giving processes with deadlines a higher priority.</li>

<li>Starvation of lower-priority processes is possible with large numbers of high-priority processes queuing for CPU time.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Round-robin_scheduling">Round-robin scheduling</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Round-robin_scheduling" title="Round-robin scheduling">Round-robin scheduling</a></div>

<p>The scheduler assigns a fixed time unit per process, and cycles through them. If process completes within that time-slice it gets terminated otherwise it is rescheduled after giving a chance to all other processes.

</p>

<ul><li>RR scheduling involves extensive overhead, especially with a small time unit.</li>

<li>Balanced throughput between FCFS/FIFO and SJF/SRTF, shorter jobs are completed faster than in FIFO and longer processes are completed faster than in SJF.</li>

<li>Good average response time, waiting time is dependent on number of processes, and not average process length.</li>

<li>Because of high waiting times, deadlines are rarely met in a pure RR system.</li>

<li>Starvation can never occur, since no priority is given. Order of time unit allocation is based upon process arrival time, similar to FIFO.</li>

<li>If Time-Slice is large it becomes FCFS/FIFO or if it is short then it becomes SJF/SRTF.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Multilevel_queue_scheduling">Multilevel queue scheduling</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Multilevel_queue" title="Multilevel queue">Multilevel queue</a></div>

<p>This is used for situations in which processes are easily divided into different groups. For example, a common division is made between foreground (interactive) processes and background (batch) processes. These two types of processes have different response-time requirements and so may have different scheduling needs. It is very useful for <a href="Shared_memory" title="Shared memory">shared memory</a> problems.

</p>

<div class="mw-heading mw-heading3"><h3 id="Work-conserving_schedulers">Work-conserving schedulers</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Work-conserving_scheduler" title="Work-conserving scheduler">Work-conserving scheduler</a></div>

<p>A <a href="Work-conserving_scheduler" title="Work-conserving scheduler">work-conserving scheduler</a> is a scheduler that always tries to keep the scheduled resources busy, if there are submitted jobs ready to be scheduled. In contrast, a non-work conserving scheduler is a scheduler that, in some cases, may leave the scheduled resources idle despite the presence of jobs ready to be scheduled.

</p>

<div class="mw-heading mw-heading3"><h3 id="Scheduling_optimization_problems">Scheduling optimization problems</h3></div>

<p>There are several scheduling problems in which the goal is to decide which job goes to which station at what time, such that the total <a href="Makespan" title="Makespan">makespan</a> is minimized:

</p>

<ul><li><a href="Job-shop_scheduling" title="Job-shop scheduling">Job-shop scheduling</a> – there are <span class="texhtml mvar" style="font-style:italic;">n</span> jobs and <span class="texhtml mvar" style="font-style:italic;">m</span> identical stations. Each job should be executed on a single machine. This is usually regarded as an online problem.</li>

<li><a href="Open-shop_scheduling" title="Open-shop scheduling">Open-shop scheduling</a> – there are <span class="texhtml mvar" style="font-style:italic;">n</span> jobs and <span class="texhtml mvar" style="font-style:italic;">m</span> different stations. Each job should spend some time at each station, in a free order.</li>

<li><a href="Flow-shop_scheduling" title="Flow-shop scheduling">Flow-shop scheduling</a> – there are <span class="texhtml mvar" style="font-style:italic;">n</span> jobs and <span class="texhtml mvar" style="font-style:italic;">m</span> different stations. Each job should spend some time at each station, in a pre-determined order.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Manual_scheduling">Manual scheduling</h3></div>

<p>A very common method in embedded systems is to schedule jobs manually. This can for example be done in a time-multiplexed fashion. Sometimes the kernel is divided in three or more parts: Manual scheduling, preemptive and interrupt level. Exact methods for scheduling jobs are often proprietary.

</p>

<ul><li>No resource starvation problems</li>

<li>Very high predictability; allows implementation of hard real-time systems</li>

<li>Almost no overhead</li>

<li>May not be optimal for all applications</li>

<li>Effectiveness is completely dependent on the implementation</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Choosing_a_scheduling_algorithm">Choosing a scheduling algorithm</h3></div>

<p>When designing an operating system, a programmer must consider which scheduling algorithm will perform best for the use the system is going to see. There is no universal <i>best</i> scheduling algorithm, and many operating systems use extended or combinations of the scheduling algorithms above.

</p><p>For example, <a href="Windows_NT" title="Windows NT">Windows NT</a>/XP/Vista uses a <a href="Multilevel_feedback_queue" title="Multilevel feedback queue">multilevel feedback queue</a>, a combination of fixed-priority preemptive scheduling, round-robin, and first in, first out algorithms. In this system, threads can dynamically increase or decrease in priority depending on if it has been serviced already, or if it has been waiting extensively. Every priority level is represented by its own queue, with <a href="Round-robin_scheduling" title="Round-robin scheduling">round-robin scheduling</a> among the high-priority threads and <a href="FIFO_(computing_and_electronics)" title="FIFO (computing and electronics)">FIFO</a> among the lower-priority ones. In this sense, response time is short for most threads, and short but critical system threads get completed very quickly. Since threads can only use one time unit of the round-robin in the highest-priority queue, starvation can be a problem for longer high-priority threads.

</p>

<div class="mw-heading mw-heading2"><h2 id="Operating_system_process_scheduler_implementations">Operating system process scheduler implementations</h2></div>

<p>The algorithm used may be as simple as <a href="Round-robin_scheduling" title="Round-robin scheduling">round-robin</a> in which each process is given equal time (for instance 1 ms, usually between 1 ms and 100 ms) in a cycling list. So, process A executes for 1 ms, then process B, then process C, then back to process A.

</p><p>More advanced algorithms take into account process priority, or the importance of the process. This allows some processes to use more time than other processes. The kernel always uses whatever resources it needs to ensure proper functioning of the system, and so can be said to have infinite priority. In <a href="Symmetric_multiprocessing" title="Symmetric multiprocessing">SMP</a> systems, <a href="Processor_affinity" title="Processor affinity">processor affinity</a> is considered to increase overall system performance, even if it may cause a process itself to run more slowly. This generally improves performance by reducing <a href="Cache_thrashing" class="mw-redirect" title="Cache thrashing">cache thrashing</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="OS/360_and_successors">OS/360 and successors</h3></div>

<p>IBM <a href="OS/360" class="mw-redirect" title="OS/360">OS/360</a> was available with three different schedulers. The differences were such that the variants were often considered three different operating systems:

</p>

<ul><li>The <i>Single Sequential Scheduler</i> option, also known as the <i>Primary Control Program (PCP)</i> provided sequential execution of a single stream of jobs.</li>

<li>The <i>Multiple Sequential Scheduler</i> option, known as <i>Multiprogramming with a Fixed Number of Tasks (MFT)</i> provided execution of multiple concurrent jobs. Execution was governed by a priority which had a default for each stream or could be requested separately for each job. MFT version II added subtasks (threads), which executed at a priority based on that of the parent job. Each job stream defined the maximum amount of memory which could be used by any job in that stream.</li>

<li>The <i>Multiple Priority Schedulers</i> option, or <i>Multiprogramming with a Variable Number of Tasks (MVT)</i>, featured subtasks from the start; each job requested the priority and memory it required before execution.</li></ul>

<p>Later virtual storage versions of MVS added a <i><a href="Workload_Manager" title="Workload Manager">Workload Manager</a></i> feature to the scheduler, which schedules processor resources according to an elaborate scheme defined by the installation.

</p>

<div class="mw-heading mw-heading3"><h3 id="Windows">Windows</h3></div>

<p>Very early <a href="MS-DOS" title="MS-DOS">MS-DOS</a> and Microsoft Windows systems were non-multitasking, and as such did not feature a scheduler. <a href="Windows_3.1x" class="mw-redirect" title="Windows 3.1x">Windows 3.1x</a> used a non-preemptive scheduler, meaning that it did not interrupt programs. It relied on the program to end or tell the OS that it didn't need the processor so that it could move on to another process. This is usually called cooperative multitasking. Windows 95 introduced a rudimentary preemptive scheduler; however, for legacy support opted to let 16-bit applications run without preemption.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

</p><p><a href="Windows_NT" title="Windows NT">Windows NT</a>-based operating systems use a multilevel feedback queue. 32 priority levels are defined, 0 through to 31, with priorities 0 through 15 being <i>normal</i> priorities and priorities 16 through 31 being soft real-time priorities, requiring privileges to assign. 0 is reserved for the Operating System. User interfaces and APIs work with priority classes for the process and the threads in the process, which are then combined by the system into the absolute priority level.

</p><p>The kernel may change the priority level of a thread depending on its I/O and CPU usage and whether it is interactive (i.e. accepts and responds to input from humans), raising the priority of interactive and I/O bounded processes and lowering that of CPU bound processes, to increase the responsiveness of interactive applications.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> The scheduler was modified in <a href="Windows_Vista" title="Windows Vista">Windows Vista</a> to use the <a href="Time_Stamp_Counter" title="Time Stamp Counter">cycle counter register</a> of modern processors to keep track of exactly how many CPU cycles a thread has executed, rather than just using an interval-timer interrupt routine.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> Vista also uses a priority scheduler for the I/O queue so that disk defragmenters and other such programs do not interfere with foreground operations.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Classic_Mac_OS_and_macOS">Classic Mac OS and macOS</h3></div>

<p>Mac OS 9 uses cooperative scheduling for threads, where one process controls multiple cooperative threads, and also provides preemptive scheduling for multiprocessing tasks. The kernel schedules multiprocessing tasks using a preemptive scheduling algorithm. All Process Manager processes run within a special multiprocessing task, called the <i>blue task</i>. Those processes are scheduled cooperatively, using a <a href="Round-robin_scheduling" title="Round-robin scheduling">round-robin scheduling</a> algorithm; a process yields control of the processor to another process by explicitly calling a blocking function such as <code>WaitNextEvent</code>. Each process has its own copy of the Thread Manager that schedules that process's threads cooperatively; a thread yields control of the processor to another thread by calling <code>YieldToAnyThread</code> or <code>YieldToThread</code>.<sup id="cite_ref-appletn2028_14-0" class="reference"><a href="#cite_note-appletn2028-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup>

</p><p>macOS uses a multilevel feedback queue, with four priority bands for threads – normal, system high priority, kernel mode only, and real-time.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> Threads are scheduled preemptively; macOS also supports cooperatively scheduled threads in its implementation of the Thread Manager in <a href="Carbon_(API)" title="Carbon (API)">Carbon</a>.<sup id="cite_ref-appletn2028_14-1" class="reference"><a href="#cite_note-appletn2028-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup>

</p>

<p>In AIX Version 4 there are three possible values for thread scheduling policy:

</p>

<ul><li>First In, First Out: Once a thread with this policy is scheduled, it runs to completion unless it is blocked, it voluntarily yields control of the CPU, or a higher-priority thread becomes dispatchable. Only fixed-priority threads can have a FIFO scheduling policy.</li>

<li>Round Robin: This is similar to the AIX Version 3 scheduler round-robin scheme based on 10 ms time slices. When a RR thread has control at the end of the time slice, it moves to the tail of the queue of dispatchable threads of its priority. Only fixed-priority threads can have a Round Robin scheduling policy.</li>

<li>OTHER: This policy is defined by POSIX1003.4a as implementation-defined. In AIX Version 4, this policy is defined to be equivalent to RR, except that it applies to threads with non-fixed priority. The recalculation of the running thread's priority value at each clock interrupt means that a thread may lose control because its priority value has risen above that of another dispatchable thread. This is the AIX Version 3 behavior.</li></ul>

<p>Threads are primarily of interest for applications that currently consist of several asynchronous processes. These applications might impose a lighter load on the system if converted to a multithreaded structure.

</p><p>AIX 5 implements the following scheduling policies: FIFO, round robin, and a fair round robin. The FIFO policy has three different implementations: FIFO, FIFO2, and FIFO3. The round robin policy is named SCHED_RR in AIX, and the fair round robin is called SCHED_OTHER.<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Linux">Linux</h3></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Linux_kernel#Scheduling" title="Linux kernel">Linux kernel § Scheduling</a></div>

<div class="mw-heading mw-heading4"><h4 id="Linux_1.2">Linux 1.2</h4></div>

<p>Linux 1.2 used a <a href="Round-robin_scheduling" title="Round-robin scheduling">round-robin scheduling</a> policy.<sup id="cite_ref-:0_17-0" class="reference"><a href="#cite_note-:0-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading4"><h4 id="Linux_2.2">Linux 2.2</h4></div><p>

Linux 2.2 added scheduling classes and support for <a href="Symmetric_multiprocessing" title="Symmetric multiprocessing">symmetric multiprocessing</a> (SMP).<sup id="cite_ref-:0_17-1" class="reference"><a href="#cite_note-:0-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup></p>

<div class="mw-heading mw-heading4"><h4 id="Linux_2.4">Linux 2.4</h4></div>

<p>In <a href="Linux" title="Linux">Linux</a> 2.4,<sup id="cite_ref-:0_17-2" class="reference"><a href="#cite_note-:0-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> an <a href="O(n)_scheduler" title="O(n) scheduler">O(n) scheduler</a> with a <a href="Multilevel_feedback_queue" title="Multilevel feedback queue">multilevel feedback queue</a> with priority levels ranging from 0 to 140 was used; 0–99 are reserved for real-time tasks and 100–140 are considered <a href="Nice_(Unix)" title="Nice (Unix)">nice</a> task levels. For real-time tasks, the time quantum for switching processes was approximately 200 ms, and for nice tasks approximately 10 ms. The scheduler ran through the <a href="Run_queue" title="Run queue">run queue</a> of all ready processes, letting the highest priority processes go first and run through their time slices, after which they will be placed in an expired queue. When the active queue is empty the expired queue will become the active queue and vice versa.

</p><p>However, some enterprise <a href="Linux_distributions" class="mw-redirect" title="Linux distributions">Linux distributions</a> such as <a href="SUSE_Linux_Enterprise_Server" class="mw-redirect" title="SUSE Linux Enterprise Server">SUSE Linux Enterprise Server</a> replaced this scheduler with a backport of the <a href="O(1)_scheduler" title="O(1) scheduler">O(1) scheduler</a> (which was maintained by <a href="Alan_Cox_(computer_programmer)" title="Alan Cox (computer programmer)">Alan Cox</a> in his Linux 2.4-ac Kernel series) to the Linux 2.4 kernel used by the distribution.

</p>

<div class="mw-heading mw-heading4"><h4 id="Linux_2.6.0_to_Linux_2.6.22">Linux 2.6.0 to Linux 2.6.22</h4></div>

<p>In versions 2.6.0 to 2.6.22, the kernel used an <a href="O(1)_scheduler" title="O(1) scheduler">O(1) scheduler</a> developed by <a href="Ingo_Molnar" class="mw-redirect" title="Ingo Molnar">Ingo Molnar</a> and many other kernel developers during the Linux 2.5 development. For many kernel in time frame, <a href="Con_Kolivas" title="Con Kolivas">Con Kolivas</a> developed patch sets which improved interactivity with this scheduler or even replaced it with his own schedulers.

</p>

<div class="mw-heading mw-heading4"><h4 id="Linux_2.6.23_to_Linux_6.5">Linux 2.6.23 to Linux 6.5</h4></div>

<p>Con Kolivas' work, most significantly his implementation of <a href="Fair-share_scheduling" title="Fair-share scheduling">fair scheduling</a> named <a href="Rotating_Staircase_Deadline" class="mw-redirect" title="Rotating Staircase Deadline">Rotating Staircase Deadline</a> (RSDL), inspired Ingo Molnár to develop the <a href="Completely_Fair_Scheduler" title="Completely Fair Scheduler">Completely Fair Scheduler</a> (CFS) as a replacement for the earlier <a href="O(1)_scheduler" title="O(1) scheduler">O(1) scheduler</a>, crediting Kolivas in his announcement.<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> CFS is the first implementation of a fair queuing <a href="Process_scheduler" class="mw-redirect" title="Process scheduler">process scheduler</a> widely used in a general-purpose operating system.<sup id="cite_ref-dwrr_19-0" class="reference"><a href="#cite_note-dwrr-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup>

</p><p>The CFS uses a well-studied, classic scheduling algorithm called <a href="Fair_queuing" title="Fair queuing">fair queuing</a> originally invented for <a href="Packet_network" class="mw-redirect" title="Packet network">packet networks</a>. Fair queuing had been previously applied to CPU scheduling under the name <a href="Stride_scheduling" title="Stride scheduling">stride scheduling</a>. The fair queuing CFS scheduler has a scheduling complexity of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log N)}</annotation>

</semantics>

</math></span><img src="./14eea297b4387decf341763c39dc038e05744272.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.005ex; height:2.843ex;" alt="{\displaystyle O(\log N)}" loading="lazy"></span>, where <span class="texhtml mvar" style="font-style:italic;">N</span> is the number of tasks in the <a href="Run_queue" title="Run queue">runqueue</a>. Choosing a task can be done in constant time, but reinserting a task after it has run requires <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log N)}</annotation>

</semantics>

</p><p>The <a href="Brain_Fuck_Scheduler" title="Brain Fuck Scheduler">Brain Fuck Scheduler</a>, also created by Con Kolivas, is an alternative to the CFS.

</p>

<div class="mw-heading mw-heading4"><h4 id="Linux_6.6">Linux 6.6</h4></div>

<p>In 2023, Peter Zijlstra proposed replacing CFS with an <a href="Earliest_eligible_virtual_deadline_first_scheduling" title="Earliest eligible virtual deadline first scheduling">earliest eligible virtual deadline first scheduling</a> (EEVDF) process scheduler.<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup> The aim was to remove the need for CFS <i>latency nice</i> patches.<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading4"><h4 id="Linux_6.12">Linux 6.12</h4></div>

<p>Linux 6.12 added support for <a href="User_space_and_kernel_space" title="User space and kernel space">userspace</a> scheduler extensions, also known as sched_ext.<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup> These schedulers can be installed and replace the default scheduler.<sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="FreeBSD">FreeBSD</h3></div>

<p><a href="FreeBSD" title="FreeBSD">FreeBSD</a> uses a multilevel feedback queue with priorities ranging from 0–255. 0–63 are reserved for interrupts, 64–127 for the top half of the kernel, 128–159 for real-time user threads, 160–223 for time-shared user threads, and 224–255 for idle user threads. Also, like Linux, it uses the active queue setup, but it also has an idle queue.<sup id="cite_ref-opensolaris-queue_25-0" class="reference"><a href="#cite_note-opensolaris-queue-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="NetBSD">NetBSD</h3></div>

<p><a href="NetBSD" title="NetBSD">NetBSD</a> uses a multilevel feedback queue with priorities ranging from 0–223. 0–63 are reserved for time-shared threads (default, SCHED_OTHER policy), 64–95 for user threads which entered <a href="Kernel_space" class="mw-redirect" title="Kernel space">kernel space</a>, 96-128 for kernel threads, 128–191 for user real-time threads (SCHED_FIFO and SCHED_RR policies), and 192–223 for <a href="Interrupt" title="Interrupt">software interrupts</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Solaris">Solaris</h3></div>

<p><a href="Solaris_(operating_system)" class="mw-redirect" title="Solaris (operating system)">Solaris</a> uses a multilevel feedback queue with priorities ranging between 0 and 169. Priorities 0–59 are reserved for time-shared threads, 60–99 for system threads, 100–159 for real-time threads, and 160–169 for low priority interrupts. Unlike Linux,<sup id="cite_ref-opensolaris-queue_25-1" class="reference"><a href="#cite_note-opensolaris-queue-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup> when a process is done using its time quantum, it is given a new priority and put back in the queue. Solaris 9 introduced two new scheduling classes, namely fixed-priority class and fair share class. The threads with fixed priority have the same priority range as that of the time-sharing class, but their priorities are not dynamically adjusted. The fair scheduling class uses CPU <i>shares</i> to prioritize threads for scheduling decisions. CPU shares indicate the entitlement to CPU resources. They are allocated to a set of processes, which are collectively known as a project.<sup id="cite_ref-Galvin_7-2" class="reference"><a href="#cite_note-Galvin-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Summary">Summary</h3></div>

<th>Operating System

</th>

<th>Preemption

</th>

<th>Algorithm

</th></tr>

<tr>

<td><a href="Amiga_OS" class="mw-redirect" title="Amiga OS">Amiga OS</a>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</td>

<td>Prioritized <a href="Round-robin_scheduling" title="Round-robin scheduling">round-robin scheduling</a>

</td></tr>

<tr>

<td><a href="FreeBSD" title="FreeBSD">FreeBSD</a>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</td>

<td><a href="Multilevel_feedback_queue" title="Multilevel feedback queue">Multilevel feedback queue</a>

</td></tr>

<tr>

<td><a href="Linux_kernel" title="Linux kernel">Linux kernel</a> before 2.6.0

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</td>

<td><a href="Multilevel_feedback_queue" title="Multilevel feedback queue">Multilevel feedback queue</a>

</td></tr>

<tr>

<td>Linux kernel 2.6.0–2.6.23

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</td>

<td><a href="O(1)_scheduler" title="O(1) scheduler">O(1) scheduler</a>

</td></tr>

<tr>

<td>Linux kernel 2.6.23–6.6

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</td>

<td><a href="Completely_Fair_Scheduler" title="Completely Fair Scheduler">Completely Fair Scheduler</a>

</td></tr>

<tr>

<td>Linux kernel 6.6 and later

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</td>

<td><a href="Earliest_eligible_virtual_deadline_first_scheduling" title="Earliest eligible virtual deadline first scheduling">Earliest eligible virtual deadline first scheduling</a> (EEVDF)

</td></tr>

<tr>

<td><a href="Classic_Mac_OS" title="Classic Mac OS">classic Mac OS</a> pre-9

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">None

</td>

<td><a href="Cooperative_scheduler" class="mw-redirect" title="Cooperative scheduler">Cooperative scheduler</a>

</td></tr>

<tr>

</td>

<td style="background: #FF8; color:black; vertical-align: middle; text-align: center;" class="table-maybe">Some

</td>

<td>Preemptive scheduler for MP tasks, and cooperative for processes and threads

</td></tr>

<tr>

<td><a href="MacOS" title="MacOS">macOS</a>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</td>

<td><a href="Multilevel_feedback_queue" title="Multilevel feedback queue">Multilevel feedback queue</a>

</td></tr>

<tr>

<td><a href="NetBSD" title="NetBSD">NetBSD</a>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</td>

<td><a href="Multilevel_feedback_queue" title="Multilevel feedback queue">Multilevel feedback queue</a>

</td></tr>

<tr>

<td><a href="Solaris_(operating_system)" class="mw-redirect" title="Solaris (operating system)">Solaris</a>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</td>

<td><a href="Multilevel_feedback_queue" title="Multilevel feedback queue">Multilevel feedback queue</a>

</td></tr>

<tr>

<td><a href="Windows_3.1x" class="mw-redirect" title="Windows 3.1x">Windows 3.1x</a>

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">None

</td>

<td><a href="Cooperative_scheduler" class="mw-redirect" title="Cooperative scheduler">Cooperative scheduler</a>

</td></tr>

<tr>

<td><a href="Windows_95" title="Windows 95">Windows 95</a>, <a href="Windows_98" title="Windows 98">98</a>, <a href="Windows_Me" title="Windows Me">Me</a>

</td>

<td style="background: #FF8; color:black; vertical-align: middle; text-align: center;" class="table-maybe">Half

</td>

<td>Preemptive scheduler for 32-bit processes, and cooperative for 16-bit processes

</td></tr>

<tr>

<td><a href="Windows_NT" title="Windows NT">Windows NT</a> (including 2000, XP, Vista, 7, and Server)

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes

</td>

<td><a href="Multilevel_feedback_queue" title="Multilevel feedback queue">Multilevel feedback queue</a>

</td></tr></tbody></table>

/* start https://en.wikipedia.org/ */

.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}

/* end https://en.wikipedia.org/ */

</style><div class="div-col" style="column-width: 20em;">

<ul><li><a href="Activity_selection_problem" title="Activity selection problem">Activity selection problem</a></li>

<li><a href="Aging_(scheduling)" title="Aging (scheduling)">Aging (scheduling)</a></li>

<li><a href="Automated_planning_and_scheduling" title="Automated planning and scheduling">Automated planning and scheduling</a></li>

<li><a href="Cyclic_executive" title="Cyclic executive">Cyclic executive</a></li>

<li><a href="Dynamic_priority_scheduling" title="Dynamic priority scheduling">Dynamic priority scheduling</a></li>

<li><a href="Foreground-background" title="Foreground-background">Foreground-background</a></li>

<li><a href="Interruptible_operating_system" title="Interruptible operating system">Interruptible operating system</a></li>

<li><a href="Least_slack_time_scheduling" title="Least slack time scheduling">Least slack time scheduling</a></li>

<li><a href="Lottery_scheduling" title="Lottery scheduling">Lottery scheduling</a></li>

<li><a href="Priority_inversion" title="Priority inversion">Priority inversion</a></li>

<li><a href="Process_states" class="mw-redirect" title="Process states">Process states</a></li>

<li><a href="Queuing_theory" class="mw-redirect" title="Queuing theory">Queuing theory</a></li>

<li><a href="Rate-monotonic_scheduling" title="Rate-monotonic scheduling">Rate-monotonic scheduling</a></li>

<li><a href="Scheduling_(production_processes)" title="Scheduling (production processes)">Scheduling (production processes)</a></li>

<li><a href="Stochastic_scheduling" title="Stochastic scheduling">Stochastic scheduling</a></li>

<li><a href="Time-utility_function" title="Time-utility function">Time-utility function</a></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFC._L.James_W.1973" class="citation journal cs1">C. L., Liu; James W., Layland (January 1973). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321738.321743">"Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment"</a>. <i>Journal of the ACM</i>. <b>20</b> (1). ACM: <span class="nowrap">46–</span>61. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321738.321743">10.1145/321738.321743</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207669821">207669821</a>. <q>We define the response time of a request for a certain task to be the time span between the request and the end of the response to that request.</q></cite></span>

</li>

<li id="cite_note-kleinrock1976-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-kleinrock1976_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFKleinrock1976" class="citation book cs1">Kleinrock, Leonard (1976). <a rel="nofollow" class="external text" href="https://archive.org/details/queueingsystems00klei/page/171"><i>Queueing Systems, Vol. 2: Computer Applications</i></a> (1 ed.). Wiley-Interscience. p. <a rel="nofollow" class="external text" href="https://archive.org/details/queueingsystems00klei/page/171">171</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>047149111X</bdi>. <q>For a customer requiring x sec of service, his response time will equal his service time x plus his waiting time.</q></cite></span>

</li>

<li id="cite_note-feitelson2014-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-feitelson2014_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFFeitelson2015" class="citation book cs1">Feitelson, Dror G. (2015). <a rel="nofollow" class="external text" href="http://www.cs.huji.ac.il/~feit/wlmod/"><i>Workload Modeling for Computer Systems Performance Evaluation</i></a>. Cambridge University Press. Section 8.4 (Page 422) in Version 1.03 of the freely available manuscript. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781107078239</bdi><span class="reference-accessdate">. Retrieved <span class="nowrap">2015-10-17</span></span>. <q>if we denote the time that a job waits in the queue by t<sub>w</sub>, and the time it actually runs by t<sub>r</sub>, then the response time is r = t<sub>w</sub> + t<sub>r</sub>.</q></cite></span>

</li>

<li id="cite_note-silberschatz2012-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-silberschatz2012_4-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFSilberschatzGalvinGagne2012" class="citation book cs1">Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2012). <i>Operating System Concepts</i> (9 ed.). Wiley Publishing. p. 187. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0470128725</bdi>. <q>In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response.</q></cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFPaul_Krzyzanowski2014" class="citation web cs1">Paul Krzyzanowski (2014-02-19). <a rel="nofollow" class="external text" href="https://www.cs.rutgers.edu/~pxk/416/notes/07-scheduling.html">"Process Scheduling: Who gets to run next?"</a>. <i>cs.rutgers.edu</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2023-06-19</span></span>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFRaphael_Finkel1988" class="citation book cs1"><a href="Raphael_Finkel" title="Raphael Finkel">Raphael Finkel</a> (1988). "Chapter 2: Time Management". <a rel="nofollow" class="external text" href="https://www.yumpu.com/en/document/read/32199214/an-operating-systems-vade-mecum"><i>An Operating Systems Vade Mecum</i></a>. Prentice Hall. p. 27.</cite></span>

</li>

<li id="cite_note-Galvin-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-Galvin_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Galvin_7-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Galvin_7-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFAbraham_SilberschatzPeter_Baer_GalvinGreg_Gagne2013" class="citation book cs1"><a href="Abraham_Silberschatz" title="Abraham Silberschatz">Abraham Silberschatz</a>; Peter Baer Galvin; Greg Gagne (2013). <i>Operating System Concepts</i>. Vol. 9. John Wiley & Sons, Inc. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-118-06333-0</bdi>.</cite></span>

</li>

Robert Kroeger (2004).

<a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.3977&rep=rep1&type=pdf">"Admission Control for Independently-authored Realtime Applications"</a>.

UWSpace.

<a rel="nofollow" class="external free" href="http://hdl.handle.net/10012/1170">http://hdl.handle.net/10012/1170</a> .

Section "2.6 Admission Control".

p. 33.</span>

</li>

<li id="cite_note-Miao-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-Miao_9-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFGuowang_MiaoJens_ZanderKi_Won_SungBen_Slimane2016" class="citation book cs1"><a href="Guowang_Miao" title="Guowang Miao">Guowang Miao</a>; Jens Zander; Ki Won Sung; Ben Slimane (2016). <i>Fundamentals of Mobile Data Networks</i>. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1107143210</bdi>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://web.archive.org/web/*/www.jgcampbell.com/caos/html/node13.html">Early Windows</a> at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> (archive index)</span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite id="CITEREFSriram_Krishnan" class="citation web cs1">Sriram Krishnan. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120722015555/http://sriramk.com/schedulers.html">"A Tale of Two Schedulers Windows NT and Windows CE"</a>. Archived from <a rel="nofollow" class="external text" href="http://sriramk.com/schedulers.html">the original</a> on July 22, 2012.</cite></span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://technet.microsoft.com/en-us/magazine/cc162494.aspx">"Windows Administration: Inside the Windows Vista Kernel: Part 1"</a>. <i>Technet.microsoft.com</i>. 2016-11-14<span class="reference-accessdate">. Retrieved <span class="nowrap">2016-12-09</span></span>.</cite></span>

</li>

<li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20080219174631/http://blog.gabefrost.com/?p=25">"Archived copy"</a>. <i>blog.gabefrost.com</i>. Archived from <a rel="nofollow" class="external text" href="http://blog.gabefrost.com/?p=25">the original</a> on 19 February 2008<span class="reference-accessdate">. Retrieved <span class="nowrap">15 January</span> 2022</span>.</cite><span class="cs1-maint citation-comment"><code class="cs1-code">{{cite web}}</code>: CS1 maint: archived copy as title (link)</span></span>

</li>

<li id="cite_note-appletn2028-14"><span class="mw-cite-backlink">^ <a href="#cite_ref-appletn2028_14-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-appletn2028_14-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://developer.apple.com/library/archive/technotes/tn/tn2028.html">"Technical Note TN2028: Threading Architectures"</a>. <i>developer.apple.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-01-15</span></span>.</cite></span>

</li>

<li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://developer.apple.com/library/archive/documentation/Darwin/Conceptual/KernelProgramming/scheduler/scheduler.html">"Mach Scheduling and Thread Interfaces"</a>. <i>developer.apple.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-01-15</span></span>.</cite></span>

</li>

<li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external autonumber" href="http://www.ibm.com/developerworks/aix/library/au-aix5_cpu/index.html#N100F6">[1]</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110811094049/http://www.ibm.com/developerworks/aix/library/au-aix5_cpu/index.html">Archived</a> 2011-08-11 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></span>

</li>

<li id="cite_note-:0-17"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_17-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_17-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:0_17-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFJones2018" class="citation web cs1">Jones, M. (2018-09-18) [first published on 2009-12-14]. <a rel="nofollow" class="external text" href="https://developer.ibm.com/tutorials/l-completely-fair-scheduler/">"Inside the Linux 2.6 Completely Fair Scheduler"</a>. <i>developer.ibm.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2024-02-07</span></span>.</cite></span>

</li>

<li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><cite id="CITEREFMolnár2007" class="citation mailinglist cs1"><a href="Ingo_Moln%C3%A1r" title="Ingo Molnár">Molnár, Ingo</a> (2007-04-13). <a rel="nofollow" class="external text" href="https://lwn.net/Articles/230501/">"[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]"</a>. <i>linux-kernel</i> (Mailing list).</cite></span>

</li>

<li id="cite_note-dwrr-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-dwrr_19-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFTong_LiDan_BaumbergerScott_Hahn" class="citation web cs1">Tong Li; Dan Baumberger; Scott Hahn. <a rel="nofollow" class="external text" href="http://happyli.org/tongli/papers/dwrr.pdf">"Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin"</a> <span class="cs1-format">(PDF)</span>. <i>Happyli.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2016-12-09</span></span>.</cite></span>

</li>

<li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.phoronix.com/news/Linux-6.6-EEVDF-Likely">"EEVDF Scheduler May Be Ready For Landing With Linux 6.6"</a>. <i><a href="Phoronix" class="mw-redirect" title="Phoronix">Phoronix</a></i><span class="reference-accessdate">. Retrieved <span class="nowrap">2023-08-31</span></span>.</cite></span>

</li>

<li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.phoronix.com/news/Linux-6.6-EEVDF-Merged">"EEVDF Scheduler Merged For Linux 6.6, Intel Hybrid Cluster Scheduling Re-Introduced"</a>. <i>www.phoronix.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2024-02-07</span></span>.</cite></span>

</li>

<li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://lwn.net/Articles/925371/">"An EEVDF CPU scheduler for Linux [LWN.net]"</a>. <i><a href="LWN.net" title="LWN.net">LWN.net</a></i><span class="reference-accessdate">. Retrieved <span class="nowrap">2023-08-31</span></span>.</cite></span>

</li>

<li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.phoronix.com/news/Linux-6.12-Lands-sched-ext">"Sched_ext Merged For Linux 6.12 - Scheduling Policies As BPF Programs"</a>. <i>www.phoronix.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2025-02-10</span></span>.</cite></span>

</li>

<li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://en.opensuse.org/Pluggable_CPU_schedulers">"Pluggable CPU schedulers - openSUSE Wiki"</a>. <i>en.opensuse.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2025-02-10</span></span>.</cite></span>

</li>

<li id="cite_note-opensolaris-queue-25"><span class="mw-cite-backlink">^ <a href="#cite_ref-opensolaris-queue_25-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-opensolaris-queue_25-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20080807124435/http://cn.opensolaris.org/files/solaris_linux_bsd_cmp.pdf">"Comparison of Solaris, Linux, and FreeBSD Kernels"</a> <span class="cs1-format">(PDF)</span>. Archived from <a rel="nofollow" class="external text" href="http://cn.opensolaris.org/files/solaris_linux_bsd_cmp.pdf">the original</a> <span class="cs1-format">(PDF)</span> on August 7, 2008.</cite></span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFBłażewiczEckerPeschSchmidt2001" class="citation book cs1">Błażewicz, Jacek; Ecker, K.H.; Pesch, E.; Schmidt, G.; Weglarz, J. (2001). <i>Scheduling computer and manufacturing processes</i> (2 ed.). Berlin [u.a.]: Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-41931-4</bdi>.</cite></li>

<li><cite id="CITEREFStallings,_William2004" class="citation book cs1">Stallings, William (2004). <a rel="nofollow" class="external text" href="https://archive.org/details/operatingsystems00stal"><i>Operating Systems Internals and Design Principles</i></a> (fourth ed.). Prentice Hall. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-031999-6</bdi>.</cite></li>

<li><a rel="nofollow" class="external text" href="https://github.com/bdaehlie/linux-cpu-scheduler-docs/">Information on the Linux 2.6 O(1)-scheduler</a></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://pages.cs.wisc.edu/~remzi/OSTEP/">Operating Systems: Three Easy Pieces</a> by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevant chapters: <a rel="nofollow" class="external text" href="http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf">Scheduling: Introduction</a> <a rel="nofollow" class="external text" href="http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf">Multi-level Feedback Queue</a> <a rel="nofollow" class="external text" href="http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-lottery.pdf">Proportional-share Scheduling</a> <a rel="nofollow" class="external text" href="http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-multi.pdf">Multiprocessor Scheduling</a></li>

<li><a rel="nofollow" class="external text" href="http://www.cs.sunysb.edu/~algorith/files/scheduling.shtml">Brief discussion of Job Scheduling algorithms</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20060613130106/http://oreilly.com/catalog/linuxkernel/chapter/ch10.html">Understanding the Linux Kernel: Chapter 10 Process Scheduling</a></li>

<li><a rel="nofollow" class="external text" href="http://kerneltrap.org/scheduler">Kerneltrap: Linux kernel scheduler articles</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20110811094049/http://www.ibm.com/developerworks/aix/library/au-aix5_cpu/index.html#N100F6">AIX CPU monitoring and tuning</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/bdaehlie/linux-cpu-scheduler-docs/">Josh Aas' introduction to the Linux 2.6.8.1 CPU scheduler implementation</a></li>

<li>Peter Brucker, Sigrid Knust. Complexity results for scheduling problems <a rel="nofollow" class="external autonumber" href="http://www.mathematik.uni-osnabrueck.de/research/OR/class/">[2]</a></li>

<li><a rel="nofollow" class="external text" href="http://rtime.felk.cvut.cz/scheduling-toolbox">TORSCHE Scheduling Toolbox for Matlab</a> is a toolbox of scheduling and graph algorithms.</li>

<li><a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6226795">A survey on cellular networks packet scheduling</a></li>

<li><a rel="nofollow" class="external text" href="https://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/43438.pdf">Large-scale cluster management at Google with Borg</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Processor_scheduling67" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Processor_scheduling67" style="font-size:114%;margin:0 4em"></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Algorithms</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Deadline-monotonic_scheduling" title="Deadline-monotonic scheduling">Deadline-monotonic</a></li>

<li><a href="Earliest_deadline_first_scheduling" title="Earliest deadline first scheduling">Earliest deadline</a></li>

<li><a href="Earliest_eligible_virtual_deadline_first_scheduling" title="Earliest eligible virtual deadline first scheduling">Earliest eligible virtual deadline first</a></li>

<li><a href="Fair-share_scheduling" title="Fair-share scheduling">Fair-share</a></li>

<li><a href="Fixed-priority_pre-emptive_scheduling" title="Fixed-priority pre-emptive scheduling">Fixed-priority pre-emptive</a></li>

<li><a href="Foreground-background" title="Foreground-background">Foreground-background</a></li>

<li><a href="Generalized_foreground-background" title="Generalized foreground-background">Generalized foreground-background</a></li>

<li><a href="Highest_response_ratio_next" title="Highest response ratio next">Highest response ratio next</a></li>

<li><a href="Lottery_scheduling" title="Lottery scheduling">Lottery</a></li>

<li><a href="Multilevel_feedback_queue" title="Multilevel feedback queue">Multilevel feedback queue</a></li>

<li><a href="Process_Contention_Scope" class="mw-redirect" title="Process Contention Scope">Process Contention Scope</a></li>

<li><a href="Proportional_share_scheduling" title="Proportional share scheduling">Proportional share</a></li>

<li><a href="Rate-monotonic_scheduling" title="Rate-monotonic scheduling">Rate-monotonic</a></li>

<li><a href="Round-robin_scheduling" title="Round-robin scheduling">Round-robin</a></li>

<li><a href="Shortest_job_next" title="Shortest job next">Shortest job next</a></li>

<li><a href="Shortest_remaining_time" title="Shortest remaining time">Shortest remaining time</a></li>

<li><a href="Statistical_time-division_multiplexing" title="Statistical time-division multiplexing">Statistical time-division multiplexing</a></li>

<li><a href="Stride_scheduling" title="Stride scheduling">Stride</a></li>

<li><a href="Two-level_scheduling" title="Two-level scheduling">Two-level</a></li>

<li><a href="Windows_NT_processor_scheduling" title="Windows NT processor scheduling">Windows NT</a></li>

<li><a href="YDS_algorithm" title="YDS algorithm">YDS algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Linux</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Brain_Fuck_Scheduler" title="Brain Fuck Scheduler">Brain Fuck</a></li>

<li><a href="Completely_Fair_Scheduler" title="Completely Fair Scheduler">Completely Fair</a></li>

<li><a href="SCHED_DEADLINE" title="SCHED DEADLINE">SCHED DEADLINE</a></li>

<li><a href="SCHED_FIFO" class="mw-redirect" title="SCHED FIFO">SCHED FIFO</a></li>

<li><a href="SCHED_NORMAL" class="mw-redirect" title="SCHED NORMAL">SCHED NORMAL</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Processor_affinity" title="Processor affinity">Processor affinity</a></li>

<li><a href="Starvation_(computer_science)" title="Starvation (computer science)">Starvation</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Operating_systems310" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Operating_systems310" style="font-size:114%;margin:0 4em"><a href="Operating_system" title="Operating system">Operating systems</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Comparison_of_operating_systems" title="Comparison of operating systems">Comparison</a></li>

<li><a href="Forensic_software_engineering" title="Forensic software engineering">Forensic engineering</a></li>

<li><a href="History_of_operating_systems" title="History of operating systems">History</a></li>

<li><a href="Timeline_of_operating_systems" title="Timeline of operating systems">Timeline</a></li>

<li><a href="Usage_share_of_operating_systems" title="Usage share of operating systems">Usage share</a></li>

<li><a href="Comparison_of_user_features_of_operating_systems" title="Comparison of user features of operating systems">User features comparison</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Variants</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Disk_operating_system" title="Disk operating system">Disk operating system</a></li>

<li><a href="Distributed_operating_system" title="Distributed operating system">Distributed operating system</a></li>

<li><a href="Embedded_operating_system" title="Embedded operating system">Embedded operating system</a></li>

<li><a href="Hobbyist_operating_system" title="Hobbyist operating system">Hobbyist operating system</a></li>

<li><a href="Just_enough_operating_system" title="Just enough operating system">Just enough operating system</a></li>

<li><a href="Mobile_operating_system" title="Mobile operating system">Mobile operating system</a></li>

<li><a href="Network_operating_system" title="Network operating system">Network operating system</a></li>

<li><a href="Object-oriented_operating_system" title="Object-oriented operating system">Object-oriented operating system</a></li>

<li><a href="Real-time_operating_system" title="Real-time operating system">Real-time operating system</a></li>

<li><a href="Supercomputer_operating_system" title="Supercomputer operating system">Supercomputer operating system</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Kernel_(operating_system)" title="Kernel (operating system)">Kernel</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:6em"><a href="Computer_architecture" title="Computer architecture">Architectures</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Exokernel" title="Exokernel">Exokernel</a></li>

<li><a href="Hybrid_kernel" title="Hybrid kernel">Hybrid</a></li>

<li><a href="Microkernel" title="Microkernel">Microkernel</a></li>

<li><a href="Monolithic_kernel" title="Monolithic kernel">Monolithic</a></li>

<li><a href="Multikernel" title="Multikernel">Multikernel</a></li>

<li><a href="Vkernel" title="Vkernel">vkernel</a></li>

<li><a href="Rump_kernel" title="Rump kernel">Rump kernel</a></li>

<li><a href="Unikernel" title="Unikernel">Unikernel</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:6em">Components</th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Device_driver" title="Device driver">Device driver</a></li>

<li><a href="Loadable_kernel_module" title="Loadable kernel module">Loadable kernel module</a></li>

<li><a href="User_space_and_kernel_space" title="User space and kernel space">User space and kernel space</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Process_management_(computing)" title="Process management (computing)">Process management</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:6em">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Computer_multitasking" title="Computer multitasking">Computer multitasking</a> (<a href="Cooperative_multitasking" title="Cooperative multitasking">Cooperative</a>, <a href="Preemption_(computing)" title="Preemption (computing)">Preemptive</a>)</li>

<li><a href="Context_switch" title="Context switch">Context switch</a></li>

<li><a href="Interrupt" title="Interrupt">Interrupt</a></li>

<li><a href="Process_(computing)" title="Process (computing)">Process</a></li>

<li><a href="Process_control_block" title="Process control block">Process control block</a></li>

<li><a href="Thread_(computing)" title="Thread (computing)">Thread</a></li>

<li><a href="Time-sharing" title="Time-sharing">Time-sharing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:6em"></th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Fixed-priority_pre-emptive_scheduling" title="Fixed-priority pre-emptive scheduling">Fixed-priority preemptive</a></li>

<li><a href="Multilevel_feedback_queue" title="Multilevel feedback queue">Multilevel feedback queue</a></li>

<li><a href="Round-robin_scheduling" title="Round-robin scheduling">Round-robin</a></li>

<li><a href="Shortest_job_next" title="Shortest job next">Shortest job next</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Memory_management_(operating_systems)" title="Memory management (operating systems)">Memory management</a>,<br><a href="System_resource" title="System resource">resource</a> protection</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bus_error" title="Bus error">Bus error</a></li>

<li><a href="General_protection_fault" title="General protection fault">General protection fault</a></li>

<li><a href="Memory_paging" title="Memory paging">Memory paging</a></li>

<li><a href="Memory_protection" title="Memory protection">Memory protection</a></li>

<li><a href="Protection_ring" title="Protection ring">Protection ring</a></li>

<li><a href="Segmentation_fault" title="Segmentation fault">Segmentation fault</a></li>

<li><a href="Virtual_memory" title="Virtual memory">Virtual memory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Non-volatile_memory" title="Non-volatile memory">Storage</a> access,<br><a href="File_system" title="File system">file systems</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Booting#BOOT-LOADER" title="Booting">Boot loader</a></li>

<li><a href="Defragmentation" title="Defragmentation">Defragmentation</a></li>

<li><a href="Device_file" title="Device file">Device file</a></li>

<li><a href="File_attribute" title="File attribute">File attribute</a></li>

<li><a href="Inode" title="Inode">Inode</a></li>

<li><a href="Journaling_file_system" title="Journaling file system">Journal</a></li>

<li><a href="Disk_partitioning" title="Disk partitioning">Partition</a></li>

<li><a href="Virtual_file_system" title="Virtual file system">Virtual file system</a></li>

<li><a href="Virtual_tape_library" title="Virtual tape library">Virtual tape library</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Supporting concepts</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Computer_network" title="Computer network">Computer network</a></li>

<li><a href="Shell_(computing)" title="Shell (computing)">Shell</a>

<li><a href="User_interface" title="User interface">User interface</a></li></ul></li>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Software_design_patterns225" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Software_design_patterns225" style="font-size:114%;margin:0 4em"><a href="Software_design_pattern" title="Software design pattern">Software design patterns</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Design_Patterns" title="Design Patterns">Gang of Four<br>patterns</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Creational_pattern" title="Creational pattern">Creational</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abstract_factory_pattern" title="Abstract factory pattern">Abstract factory</a></li>

<li><a href="Builder_pattern" title="Builder pattern">Builder</a></li>

<li><a href="Factory_method_pattern" title="Factory method pattern">Factory method</a></li>

<li><a href="Prototype_pattern" title="Prototype pattern">Prototype</a></li>

<li><a href="Singleton_pattern" title="Singleton pattern">Singleton</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Structural_pattern" title="Structural pattern">Structural</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adapter_pattern" title="Adapter pattern">Adapter</a></li>

<li><a href="Bridge_pattern" title="Bridge pattern">Bridge</a></li>

<li><a href="Composite_pattern" title="Composite pattern">Composite</a></li>

<li><a href="Decorator_pattern" title="Decorator pattern">Decorator</a></li>

<li><a href="Facade_pattern" title="Facade pattern">Facade</a></li>

<li><a href="Flyweight_pattern" title="Flyweight pattern">Flyweight</a></li>

<li><a href="Proxy_pattern" title="Proxy pattern">Proxy</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Behavioral_pattern" title="Behavioral pattern">Behavioral</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Chain-of-responsibility_pattern" title="Chain-of-responsibility pattern">Chain of responsibility</a></li>

<li><a href="Command_pattern" title="Command pattern">Command</a></li>

<li><a href="Interpreter_pattern" title="Interpreter pattern">Interpreter</a></li>

<li><a href="Iterator_pattern" title="Iterator pattern">Iterator</a></li>

<li><a href="Mediator_pattern" title="Mediator pattern">Mediator</a></li>

<li><a href="Memento_pattern" title="Memento pattern">Memento</a></li>

<li><a href="Observer_pattern" title="Observer pattern">Observer</a></li>

<li><a href="State_pattern" title="State pattern">State</a></li>

<li><a href="Strategy_pattern" title="Strategy pattern">Strategy</a></li>

<li><a href="Template_method_pattern" title="Template method pattern">Template method</a></li>

<li><a href="Visitor_pattern" title="Visitor pattern">Visitor</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Concurrency_pattern" title="Concurrency pattern">Concurrency<br>patterns</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Active_object" title="Active object">Active object</a></li>

<li><a href="Balking_pattern" title="Balking pattern">Balking</a></li>

<li><a href="Binding_properties_pattern" title="Binding properties pattern">Binding properties</a></li>

<li><a href="Double-checked_locking" title="Double-checked locking">Double-checked locking</a></li>

<li><a href="Asynchronous_method_invocation" title="Asynchronous method invocation">Event-based asynchronous</a></li>

<li><a href="Guarded_suspension" title="Guarded suspension">Guarded suspension</a></li>

<li><a href="Monitor_(synchronization)" title="Monitor (synchronization)">Monitor</a></li>

<li><a href="Proactor_pattern" title="Proactor pattern">Proactor</a></li>

<li><a href="Reactor_pattern" title="Reactor pattern">Reactor</a></li>

<li><a href="Readers%E2%80%93writer_lock" title="Readers–writer lock">Read–write lock</a></li>

<li><a href="Scheduler_pattern" class="mw-redirect" title="Scheduler pattern">Scheduler</a></li>

<li><a href="Scheduled-task_pattern" title="Scheduled-task pattern">Scheduled-task pattern</a></li>

<li><a href="Semaphore_(programming)" title="Semaphore (programming)">Semaphore</a></li>

<li><a href="Thread_pool" title="Thread pool">Thread pool</a></li>

<li><a href="Thread-local_storage" title="Thread-local storage">Thread-local storage</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Architectural_pattern" title="Architectural pattern">Architectural<br>patterns</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Front_controller" title="Front controller">Front controller</a></li>

<li><a href="Interceptor_pattern" title="Interceptor pattern">Interceptor</a></li>

<li><a href="Specification_pattern" title="Specification pattern">Specification</a></li>

<li><a href="Publish%E2%80%93subscribe_pattern" title="Publish–subscribe pattern">Publish–subscribe</a></li>

<li><a href="Naked_objects" title="Naked objects">Naked objects</a></li>

<li><a href="Service_locator_pattern" title="Service locator pattern">Service locator</a></li>

<li><a href="Active_record_pattern" title="Active record pattern">Active record</a></li>

<li><a href="Identity_map_pattern" title="Identity map pattern">Identity map</a></li>

<li><a href="Data_access_object" title="Data access object">Data access object</a></li>

<li><a href="Data_transfer_object" title="Data transfer object">Data transfer object</a></li>

<li><a href="Inversion_of_control" title="Inversion of control">Inversion of control</a></li>

<li><a href="JSP_model_2_architecture" title="JSP model 2 architecture">Model 2</a></li>

<li><a href="Broker_pattern" title="Broker pattern">Broker</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other<br>patterns</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Blackboard_design_pattern" class="mw-redirect" title="Blackboard design pattern">Blackboard</a></li>

<li><a href="Business_delegate_pattern" title="Business delegate pattern">Business delegate</a></li>

<li><a href="Composite_entity_pattern" title="Composite entity pattern">Composite entity</a></li>

<li><a href="Dependency_injection" title="Dependency injection">Dependency injection</a></li>

<li><a href="Guard_(computer_science)" title="Guard (computer science)">Guard clause</a></li>

<li><a href="Intercepting_filter_pattern" title="Intercepting filter pattern">Intercepting filter</a></li>

<li><a href="Lazy_loading" title="Lazy loading">Lazy loading</a></li>

<li><a href="Mock_object" title="Mock object">Mock object</a></li>

<li><a href="Null_object_pattern" title="Null object pattern">Null object</a></li>

<li><a href="Object_pool_pattern" title="Object pool pattern">Object pool</a></li>

<li><a href="Servant_(design_pattern)" title="Servant (design pattern)">Servant</a></li>

<li><a href="Type_Tunnel_pattern" class="mw-redirect" title="Type Tunnel pattern">Type tunnel</a></li>

<li><a href="Method_chaining" title="Method chaining">Method chaining</a></li>

<li><a href="Delegation_pattern" title="Delegation pattern">Delegation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Books</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><i><a href="Design_Patterns" title="Design Patterns">Design Patterns</a></i></li>

<li><i><a href="Enterprise_Integration_Patterns" title="Enterprise Integration Patterns">Enterprise Integration Patterns</a></i></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">People</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Christopher_Alexander" title="Christopher Alexander">Christopher Alexander</a></li>

<li><a href="Erich_Gamma" title="Erich Gamma">Erich Gamma</a></li>

<li><a href="Ralph_Johnson_(computer_scientist)" title="Ralph Johnson (computer scientist)">Ralph Johnson</a></li>

<li><a href="John_Vlissides" title="John Vlissides">John Vlissides</a></li>

<li><a href="Grady_Booch" title="Grady Booch">Grady Booch</a></li>

<li><a href="Ward_Cunningham" title="Ward Cunningham">Ward Cunningham</a></li>

<li><a href="Martin_Fowler_(software_engineer)" title="Martin Fowler (software engineer)">Martin Fowler</a></li>

<li><a href="Robert_C._Martin" title="Robert C. Martin">Robert Martin</a></li>

<li><a href="Jim_Coplien" title="Jim Coplien">Jim Coplien</a></li>

<li><a href="Douglas_C._Schmidt" title="Douglas C. Schmidt">Douglas Schmidt</a></li>

<li><a href="Linda_Rising" title="Linda Rising">Linda Rising</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Communities</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="The_Hillside_Group" title="The Hillside Group">The Hillside Group</a></li>

<li><a href="Portland_Pattern_Repository" title="Portland Pattern Repository">Portland Pattern Repository</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">See also</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Anti-pattern" title="Anti-pattern">Anti-pattern</a></li>

<li><a href="Architectural_pattern" title="Architectural pattern">Architectural pattern</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-08" href="https://en.wikipedia.org/wiki/?title=Scheduling_(computing)&oldid=1304846873">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>